// K个逆序对数组
// 逆序对的定义如下：
// 对于数组nums的第i个和第j个元素
// 如果满足0<=i<j<nums.length 且 nums[i]>nums[j]，则为一个逆序对
// 给你两个整数n和k，找出所有包含从1到n的数字
// 且恰好拥有k个逆序对的不同的数组的个数
// 由于答案可能很大，答案对 1000000007 取模
// 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/
public class Code02_KInversePairsArray {

    // 最普通的动态规划
    // 不优化枚举
    public static int kInversePairs1(int n, int k) {
        int mod = 1000000007;
        // dp[i][j] : 1、2、3...i这些数字，形成的排列一定要有j个逆序对，请问这样的排列有几种
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++) {
                if (i > j) {
                    for (int p = 0; p <= j; p++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
                    }
                } else {
                    // i <= j
                    for (int p = j - i + 1; p <= j; p++) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][p]) % mod;
                    }
                }
            }
        }
        return dp[n][k];
    }

    // 根据观察方法1优化枚举
    // 最优解
    // 其实可以进一步空间压缩
    // 有兴趣的同学自己试试吧
    public static int kInversePairs2(int n, int k) {
        int mod = 1000000007;
        int[][] dp = new int[n + 1][k + 1];
        dp[0][0] = 1;
        // window : 窗口的累加和
        for (int i = 1, window; i <= n; i++) {
            dp[i][0] = 1;
            window = 1;
            for (int j = 1; j <= k; j++) {
                if (i > j) {
                    window = (window + dp[i - 1][j]) % mod;
                } else {
                    // i <= j
                    window = ((window + dp[i - 1][j]) % mod - dp[i - 1][j - i] + mod) % mod;
                }
                dp[i][j] = window;
            }
        }
        return dp[n][k];
    }

}